package arithmetic;

public class QuickSort {
	public static void main(String[] args) {

	}

	/**
	 * 进行递归每轮的处理
	 * 
	 * @param arr
	 *            处理的数组
	 * @param low
	 *            左侧起始位置
	 * @param high
	 *            右侧起始位置
	 * @return 中间分隔位置
	 */
	private static int doSort(int[] arr, int low, int high) {
		int lo = low;
		int hi = high;
		// （1）选取第一个元素作为标准元素，
		int key = arr[low];
		while (lo < hi) {
			// （2）从数列右边起向左查找第一个比标准元素小的数，将该数和第（1）中标准元素的位置进行交换；
			while (lo < hi && arr[hi] > key) {
				// 找到比标准元素小的数才会跳出循环
				// 找到比标准元素小的数不满足循环要求跳出
				hi--;
			}
			// 找到位置会后，进行交换处理
			// 只有找到位置时才进行交换
			arr[lo] = arr[hi];
			// （3）从数列左侧起向右查找第一个比标准元素大的数，将该数和第（2）中标准元素的为值进行交换；
			while (lo < hi && arr[lo] < key) {
				// 找到比标准元素大的数才会跳出循环
				// 找到比标准元素大的数不满足循环要求跳出
				lo++;
			}
			
			arr[hi] = arr[lo];
			// 左右交替查找结束之后，将标识变量的值放在最后空余的位置上
						arr[hi] = key;
		}
		return hi;
	}

}
